class Heap {
  constructor(compare) {
    this.heap = []
    const originCompare = compare || ((a, b) => a - b)
    this.compare = (a, b) => {
      const res = -originCompare(a, b)
      return isNaN(res) ? 0 : res
    }
  }
  size() {
    return this.heap.length
  }
  isEmpty() {
    return this.heap.length === 0
  }
  push(value) {
    this.heap.push(value)
    this.bubbleUp(this.heap.length - 1)
  }
  pop() {
    if (this.isEmpty()) return undefined
    const top = this.heap[0]
    const last = this.heap.pop()
    if (!this.isEmpty()) {
      this.heap[0] = last
      this.sinkDown(0)
    }
    return top
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      if (this.compare(this.heap[index], this.heap[parentIndex]) > 0) {
        this._swap(index, parentIndex)
        index = parentIndex
      } else break
    }
  }
  sinkDown(index) {
    let current = index
    const length = this.size()
    while (true) {
      const left = 2 * current + 1
      const right = 2 * current + 2
      let target = current
      if (left < length && this.compare(this.heap[left], this.heap[target]) > 0)
        target = left
      if (right < length && this.compare(this.heap[right], this.heap[target]) > 0)
        target = right
      if (target !== current) {
        this._swap(current, target)
        current = target
      } else break
    }
  }
  _swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
  }
}